#include <iostream>
#include <string>

using namespace std;


class Solution
{
public:
	void merge(int A[], int m, int B[], int n) {
		int i=m-1;
		int j=n-1;
		int k=m+n-1;

		while(i>=0&&j>=0)
		{
			if(A[i]>=B[j])
			{
				A[k]=A[i];
				i--;
			}
			else
			{
				A[k]=B[j];
				j--;
			}
			k--;
		}
		if(j>=0)
		{
			for(int t=j;t>=0;--t)
			{
				A[t]=B[t];
			}
		}
	}
};

int main()
{
	Solution solution;
	int a[10]={1,5,6,9,10,12};
	int b[]={2,3,5,8};
	int alen=6;
	int blen=4;
	solution.merge(a,alen,b,blen);

	int count=alen+blen-1;
	while(count>=0){
		cout<<a[count]<<"\t"<<endl;
		count--;
	}
}